home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 98 / Skunkware 98.iso / src / fileutil / fileutils-3.16.tar.gz / fileutils-3.16.tar / fileutils-3.16 / lib / memcmp.c < prev    next >
C/C++ Source or Header  |  1996-11-04  |  9KB  |  374 lines
  1. /* Copyright (C) 1991, 1993, 1995 Free Software Foundation, Inc.
  2.    Contributed by Torbjorn Granlund (tege@sics.se).
  3.  
  4. NOTE: The canonical source of this file is maintained with the GNU C Library.
  5. Bugs can be reported to bug-glibc@prep.ai.mit.edu.
  6.  
  7. This program is free software; you can redistribute it and/or modify it
  8. under the terms of the GNU General Public License as published by the
  9. Free Software Foundation; either version 2, or (at your option) any
  10. later version.
  11.  
  12. This program is distributed in the hope that it will be useful,
  13. but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15. GNU General Public License for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with this program; if not, write to the Free Software Foundation,
  19. Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  20.  
  21. #ifdef HAVE_CONFIG_H
  22. #include "config.h"
  23. #endif
  24.  
  25. #undef    __ptr_t
  26. #if defined (__cplusplus) || (defined (__STDC__) && __STDC__)
  27. #define    __ptr_t    void *
  28. #else /* Not C++ or ANSI C.  */
  29. #undef    const
  30. #define    const
  31. #define    __ptr_t    char *
  32. #endif /* C++ or ANSI C.  */
  33.  
  34. #if defined (HAVE_STRING_H) || defined (_LIBC)
  35. #include <string.h>
  36. #endif
  37.  
  38. #ifdef _LIBC
  39.  
  40. #include <memcopy.h>
  41.  
  42. #else    /* Not in the GNU C library.  */
  43.  
  44. #include <sys/types.h>
  45.  
  46. /* Type to use for aligned memory operations.
  47.    This should normally be the biggest type supported by a single load
  48.    and store.  Must be an unsigned type.  */
  49. #define    op_t    unsigned long int
  50. #define OPSIZ    (sizeof(op_t))
  51.  
  52. /* Threshold value for when to enter the unrolled loops.  */
  53. #define    OP_T_THRES    16
  54.  
  55. /* Type to use for unaligned operations.  */
  56. typedef unsigned char byte;
  57.  
  58. #ifndef WORDS_BIGENDIAN
  59. #define MERGE(w0, sh_1, w1, sh_2) (((w0) >> (sh_1)) | ((w1) << (sh_2)))
  60. #else
  61. #define MERGE(w0, sh_1, w1, sh_2) (((w0) << (sh_1)) | ((w1) >> (sh_2)))
  62. #endif
  63.  
  64. #endif    /* In the GNU C library.  */
  65.  
  66. #ifdef WORDS_BIGENDIAN
  67. #define CMP_LT_OR_GT(a, b) ((a) > (b) ? 1 : -1)
  68. #else
  69. #define CMP_LT_OR_GT(a, b) memcmp_bytes ((a), (b))
  70. #endif
  71.  
  72. /* BE VERY CAREFUL IF YOU CHANGE THIS CODE!  */
  73.  
  74. /* The strategy of this memcmp is:
  75.  
  76.    1. Compare bytes until one of the block pointers is aligned.
  77.  
  78.    2. Compare using memcmp_common_alignment or
  79.       memcmp_not_common_alignment, regarding the alignment of the other
  80.       block after the initial byte operations.  The maximum number of
  81.       full words (of type op_t) are compared in this way.
  82.  
  83.    3. Compare the few remaining bytes.  */
  84.  
  85. #ifndef WORDS_BIGENDIAN
  86. /* memcmp_bytes -- Compare A and B bytewise in the byte order of the machine.
  87.    A and B are known to be different.
  88.    This is needed only on little-endian machines.  */
  89. #ifdef  __GNUC__
  90. __inline
  91. #endif
  92. static int
  93. memcmp_bytes (a, b)
  94.      op_t a, b;
  95. {
  96.   long int srcp1 = (long int) &a;
  97.   long int srcp2 = (long int) &b;
  98.   op_t a0, b0;
  99.  
  100.   do
  101.     {
  102.       a0 = ((byte *) srcp1)[0];
  103.       b0 = ((byte *) srcp2)[0];
  104.       srcp1 += 1;
  105.       srcp2 += 1;
  106.     }
  107.   while (a0 == b0);
  108.   return a0 - b0;
  109. }
  110. #endif
  111.  
  112. /* memcmp_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN `op_t'
  113.    objects (not LEN bytes!).  Both SRCP1 and SRCP2 should be aligned for
  114.    memory operations on `op_t's.  */
  115. #ifdef    __GNUC__
  116. __inline
  117. #endif
  118. static int
  119. memcmp_common_alignment (srcp1, srcp2, len)
  120.      long int srcp1;
  121.      long int srcp2;
  122.      size_t len;
  123. {
  124.   op_t a0, a1;
  125.   op_t b0, b1;
  126.  
  127.   switch (len % 4)
  128.     {
  129.     case 2:
  130.       a0 = ((op_t *) srcp1)[0];
  131.       b0 = ((op_t *) srcp2)[0];
  132.       srcp1 -= 2 * OPSIZ;
  133.       srcp2 -= 2 * OPSIZ;
  134.       len += 2;
  135.       goto do1;
  136.     case 3:
  137.       a1 = ((op_t *) srcp1)[0];
  138.       b1 = ((op_t *) srcp2)[0];
  139.       srcp1 -= OPSIZ;
  140.       srcp2 -= OPSIZ;
  141.       len += 1;
  142.       goto do2;
  143.     case 0:
  144.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  145.     return 0;
  146.       a0 = ((op_t *) srcp1)[0];
  147.       b0 = ((op_t *) srcp2)[0];
  148.       goto do3;
  149.     case 1:
  150.       a1 = ((op_t *) srcp1)[0];
  151.       b1 = ((op_t *) srcp2)[0];
  152.       srcp1 += OPSIZ;
  153.       srcp2 += OPSIZ;
  154.       len -= 1;
  155.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  156.     goto do0;
  157.       /* Fall through.  */
  158.     }
  159.  
  160.   do
  161.     {
  162.       a0 = ((op_t *) srcp1)[0];
  163.       b0 = ((op_t *) srcp2)[0];
  164.       if (a1 != b1)
  165.     return CMP_LT_OR_GT (a1, b1);
  166.  
  167.     do3:
  168.       a1 = ((op_t *) srcp1)[1];
  169.       b1 = ((op_t *) srcp2)[1];
  170.       if (a0 != b0)
  171.     return CMP_LT_OR_GT (a0, b0);
  172.  
  173.     do2:
  174.       a0 = ((op_t *) srcp1)[2];
  175.       b0 = ((op_t *) srcp2)[2];
  176.       if (a1 != b1)
  177.     return CMP_LT_OR_GT (a1, b1);
  178.  
  179.     do1:
  180.       a1 = ((op_t *) srcp1)[3];
  181.       b1 = ((op_t *) srcp2)[3];
  182.       if (a0 != b0)
  183.     return CMP_LT_OR_GT (a0, b0);
  184.  
  185.       srcp1 += 4 * OPSIZ;
  186.       srcp2 += 4 * OPSIZ;
  187.       len -= 4;
  188.     }
  189.   while (len != 0);
  190.  
  191.   /* This is the right position for do0.  Please don't move
  192.      it into the loop.  */
  193.  do0:
  194.   if (a1 != b1)
  195.     return CMP_LT_OR_GT (a1, b1);
  196.   return 0;
  197. }
  198.  
  199. /* memcmp_not_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN
  200.    `op_t' objects (not LEN bytes!).  SRCP2 should be aligned for memory
  201.    operations on `op_t', but SRCP1 *should be unaligned*.  */
  202. #ifdef    __GNUC__
  203. __inline
  204. #endif
  205. static int
  206. memcmp_not_common_alignment (srcp1, srcp2, len)
  207.      long int srcp1;
  208.      long int srcp2;
  209.      size_t len;
  210. {
  211.   op_t a0, a1, a2, a3;
  212.   op_t b0, b1, b2, b3;
  213.   op_t x;
  214.   int shl, shr;
  215.  
  216.   /* Calculate how to shift a word read at the memory operation
  217.      aligned srcp1 to make it aligned for comparison.  */
  218.  
  219.   shl = 8 * (srcp1 % OPSIZ);
  220.   shr = 8 * OPSIZ - shl;
  221.  
  222.   /* Make SRCP1 aligned by rounding it down to the beginning of the `op_t'
  223.      it points in the middle of.  */
  224.   srcp1 &= -OPSIZ;
  225.  
  226.   switch (len % 4)
  227.     {
  228.     case 2:
  229.       a1 = ((op_t *) srcp1)[0];
  230.       a2 = ((op_t *) srcp1)[1];
  231.       b2 = ((op_t *) srcp2)[0];
  232.       srcp1 -= 1 * OPSIZ;
  233.       srcp2 -= 2 * OPSIZ;
  234.       len += 2;
  235.       goto do1;
  236.     case 3:
  237.       a0 = ((op_t *) srcp1)[0];
  238.       a1 = ((op_t *) srcp1)[1];
  239.       b1 = ((op_t *) srcp2)[0];
  240.       srcp2 -= 1 * OPSIZ;
  241.       len += 1;
  242.       goto do2;
  243.     case 0:
  244.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  245.     return 0;
  246.       a3 = ((op_t *) srcp1)[0];
  247.       a0 = ((op_t *) srcp1)[1];
  248.       b0 = ((op_t *) srcp2)[0];
  249.       srcp1 += 1 * OPSIZ;
  250.       goto do3;
  251.     case 1:
  252.       a2 = ((op_t *) srcp1)[0];
  253.       a3 = ((op_t *) srcp1)[1];
  254.       b3 = ((op_t *) srcp2)[0];
  255.       srcp1 += 2 * OPSIZ;
  256.       srcp2 += 1 * OPSIZ;
  257.       len -= 1;
  258.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  259.     goto do0;
  260.       /* Fall through.  */
  261.     }
  262.  
  263.   do
  264.     {
  265.       a0 = ((op_t *) srcp1)[0];
  266.       b0 = ((op_t *) srcp2)[0];
  267.       x = MERGE(a2, shl, a3, shr);
  268.       if (x != b3)
  269.     return CMP_LT_OR_GT (x, b3);
  270.  
  271.     do3:
  272.       a1 = ((op_t *) srcp1)[1];
  273.       b1 = ((op_t *) srcp2)[1];
  274.       x = MERGE(a3, shl, a0, shr);
  275.       if (x != b0)
  276.     return CMP_LT_OR_GT (x, b0);
  277.  
  278.     do2:
  279.       a2 = ((op_t *) srcp1)[2];
  280.       b2 = ((op_t *) srcp2)[2];
  281.       x = MERGE(a0, shl, a1, shr);
  282.       if (x != b1)
  283.     return CMP_LT_OR_GT (x, b1);
  284.  
  285.     do1:
  286.       a3 = ((op_t *) srcp1)[3];
  287.       b3 = ((op_t *) srcp2)[3];
  288.       x = MERGE(a1, shl, a2, shr);
  289.       if (x != b2)
  290.     return CMP_LT_OR_GT (x, b2);
  291.  
  292.       srcp1 += 4 * OPSIZ;
  293.       srcp2 += 4 * OPSIZ;
  294.       len -= 4;
  295.     }
  296.   while (len != 0);
  297.  
  298.   /* This is the right position for do0.  Please don't move
  299.      it into the loop.  */
  300.  do0:
  301.   x = MERGE(a2, shl, a3, shr);
  302.   if (x != b3)
  303.     return CMP_LT_OR_GT (x, b3);
  304.   return 0;
  305. }
  306.  
  307. int
  308. memcmp (s1, s2, len)
  309.      const __ptr_t s1;
  310.      const __ptr_t s2;
  311.      size_t len;
  312. {
  313.   op_t a0;
  314.   op_t b0;
  315.   long int srcp1 = (long int) s1;
  316.   long int srcp2 = (long int) s2;
  317.   op_t res;
  318.  
  319.   if (len >= OP_T_THRES)
  320.     {
  321.       /* There are at least some bytes to compare.  No need to test
  322.      for LEN == 0 in this alignment loop.  */
  323.       while (srcp2 % OPSIZ != 0)
  324.     {
  325.       a0 = ((byte *) srcp1)[0];
  326.       b0 = ((byte *) srcp2)[0];
  327.       srcp1 += 1;
  328.       srcp2 += 1;
  329.       res = a0 - b0;
  330.       if (res != 0)
  331.         return res;
  332.       len -= 1;
  333.     }
  334.  
  335.       /* SRCP2 is now aligned for memory operations on `op_t'.
  336.      SRCP1 alignment determines if we can do a simple,
  337.      aligned compare or need to shuffle bits.  */
  338.  
  339.       if (srcp1 % OPSIZ == 0)
  340.     res = memcmp_common_alignment (srcp1, srcp2, len / OPSIZ);
  341.       else
  342.     res = memcmp_not_common_alignment (srcp1, srcp2, len / OPSIZ);
  343.       if (res != 0)
  344.     return res;
  345.  
  346.       /* Number of bytes remaining in the interval [0..OPSIZ-1].  */
  347.       srcp1 += len & -OPSIZ;
  348.       srcp2 += len & -OPSIZ;
  349.       len %= OPSIZ;
  350.     }
  351.  
  352.   /* There are just a few bytes to compare.  Use byte memory operations.  */
  353.   while (len != 0)
  354.     {
  355.       a0 = ((byte *) srcp1)[0];
  356.       b0 = ((byte *) srcp2)[0];
  357.       srcp1 += 1;
  358.       srcp2 += 1;
  359.       res = a0 - b0;
  360.       if (res != 0)
  361.     return res;
  362.       len -= 1;
  363.     }
  364.  
  365.   return 0;
  366. }
  367.  
  368. #ifdef weak_alias
  369. #undef bcmp
  370. weak_alias (memcmp, bcmp)
  371. #endif
  372.  
  373.  
  374.